/*
 * =====================================================================================
 *
 *       Filename:  ACAutomation.cpp
 *
 *    Description:  
 *
 *        Version:  1.0
 *        Created:  2015/04/28 18时11分47秒
 *       Revision:  none
 *       Compiler:  gcc
 *
 *         Author:  Liu Yi (), swliuyi@gmail.com
 *   Organization:  
 *
 * =====================================================================================
 */
#include <iostream>
#include <string>
#include <cstring>
#include <cstdlib>
#include <queue>
#include  <vector>
#include  <map>
#include  <set>
using namespace std;
const int MAXC = 26;
const int MAXNODE = 1000000;

class Node
{
    public:
        int cnt;
        map<string, Node *> next;
        Node * failed;
        Node():cnt(0), failed(NULL)
    {
        next.clear();
    }
};

class ACAutomation
{
    public:
        vector<Node> * pool;
        Node * root;
        int tail;
        ACAutomation():root(new Node()), tail(0)
    {
        pool = new vector<Node>;
    }
        ~ACAutomation()
        {
            pool->clear();
            delete  pool;
        }

        void LoadDic(set<string> str)
        {
            Node * cur = root;
            set<string>::iterator it;
            for( it = str.begin() ; it != str.end() ; it++ )
            {
                string index = *it;
                if(cur->next[index] == NULL )
                {
                    Node tmp;
                    pool->push_back(tmp);
                    cur->next[index] = &((*pool)[pool->size()-1]);
                }
                cur = cur->next[index];
            }
            cur->cnt++;
        }

        void Build()
        {
            root->failed = NULL;
            queue<Node *> nodeQueue;
            nodeQueue.push(root);
            while( nodeQueue.size() )
            {
                Node * cur = nodeQueue.front();
                nodeQueue.pop();
                map<string, Node*>::iterator it;
                for( it = cur->next.begin() ; it != cur->next.end() ; it++ )
                {
                    Node * son = it->second;
                    if( son != NULL )
                    {
                        nodeQueue.push(son);
                        Node * tmp = cur->failed;
                        while( tmp != NULL && tmp->next[it->first] == NULL)
                        {
                            tmp = tmp->failed;
                        }
                        if( tmp == NULL)
                        {
                            son->failed = root; 
                        }
                        else
                        {
                            son->failed = tmp->next[it->first];
                        }
                    }
                }
            }
        }

        bool Query(vector<string> str)
        {
            int size = str.size();
            Node * cur = root;
            for( int i = 0 ; i < size ; i++ )
            {
                string index = str[i];
                while( cur->next[index] == NULL && cur != root )
                {
                    cur = cur->failed;
                }
                cur = cur->next[index];
                if( cur == NULL )
                {
                    cur = root;
                }
                if( cur->cnt )
                {
                    return true;
                }
            }
            return false;
        }
};

int main(int argc, char *argv[])
{
    if( argc < 4 )
    {
        cout<<"./this dict input output"<<endl;
    }

}
